import java.util.Stack;

public class Solution {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor1(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor1(root.right, p, q);
        if (leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree != null) {
            return leftTree;
        } else {
            return rightTree;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getpath(root, p, stack1);
        getpath(root, q, stack2);
        int stack1size = stack1.size();
        int stack2size = stack2.size();
        if (stack1size - stack2size > 0) {
            balance(stack1, stack2size);
        } else {
            balance(stack2, stack1size);
        }
        while (!stack1.empty()) {
            if (stack1.peek() == stack2.peek()) {
                return stack1.pop();
            } else {
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }

    private void balance(Stack stack, int size) {
        while (stack.size() != size) {
            stack.pop();
        }
    }

    public boolean getpath(TreeNode root, TreeNode node, Stack stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean flag1 = getpath(root.left, node, stack);
        if (flag1 == true) {
            return true;
        }
        boolean flag2 = getpath(root.right, node, stack);
        if (flag2 == true) {
            return true;
        }
        stack.pop();
        return false;
    }

    private int preindex;

    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        return buildTreechild1(preorder, inorder, 0, inorder.length);
    }

    private TreeNode buildTreechild1(int[] preorder, int[] inorder, int begin, int end) {

        if (begin > end) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[preindex]);
        int rootindex = findrootindex(inorder, begin, end, preorder[preindex]);
        preindex++;
        treeNode.left = buildTreechild1(preorder, inorder, begin, rootindex - 1);
        treeNode.right = buildTreechild1(preorder, inorder, rootindex + 1, end);
        return treeNode;
    }

    private int postindex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postindex = postorder.length - 1;
        return buildTreechild(postorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreechild(int[] postorder, int[] inorder, int begin, int end) {
        if (begin > end) {
            return null;
        }
        TreeNode treeNode = new TreeNode(postorder[postindex]);
        int rootindex = findrootindex(inorder, begin, end, postorder[postindex]);
        postindex--;
        treeNode.right =buildTreechild(postorder,  inorder,rootindex+1,end );
        treeNode.left =buildTreechild(postorder,  inorder,begin,rootindex-1 );
        return treeNode;

    }

    private int findrootindex(int[] inorder, int begin, int end, int key) {
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public String tree2str(TreeNode root) {
        StringBuffer stringBuffer = new StringBuffer();
        tree2strchild( root,stringBuffer);
        return stringBuffer.toString();
    }
    public void tree2strchild(TreeNode root,StringBuffer stringBuffer) {
        if(root==null){
            return;
        }
        stringBuffer.append(root.val);
        if(root.left!=null){
            stringBuffer.append("(");
            tree2strchild( root.left, stringBuffer);
            stringBuffer.append(")");
        }else {
            if(root.right==null){
                return;
            }else {
                stringBuffer.append("()");
            }
        }
        if(root.right!=null){
            stringBuffer.append("(");
            tree2strchild( root.right, stringBuffer);
            stringBuffer.append(")");
        }else {
           return;
        }
    }

    public void preorderprint(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                System.out.print(cur.val+" ");
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }

    public void inorderprint(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;

        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }


    public void postrderprint(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        TreeNode flag=null;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||flag==top.right){
                System.out.print(top.val+" ");
                stack.pop();
                flag=top;
            }else{
                cur=top.right;
            }
        }
    }
}
